import java.util.Random;
import java.util.Iterator;
/**
* A queue in which dequeue and sample returns random elements.
*
* @Author kbri@itu.dk , nlch@itu.dk
*/
public class RandomQueue<Item> implements Iterable<Item>
{
	public Item[] items;
	private int count;
	private Random rand;
	
	 // create an empty random queue
	public RandomQueue(){
		items = (Item[]) new Object[1];
		count = 0;
		rand = new Random();
	}
	
	 // is it empty?
	public boolean isEmpty(){
		return count==0;
	}
	
	 // return the number of elements
	public int size(){
		return items.length;
	}
	
	// rebuilds the queue with a given new size
	private void rebuild(int newSize){
		Item[] temp = (Item[]) new Object[newSize];
		for(int i = 0; i < size();i++){
			temp[i]=items[i];
		}
		items = temp;
	}
		
	 // add an item
	public void enqueue(Item item){
		if(count == size())
			rebuild(count*2);
		items[count++] = item;
	}
	
	 // return (but do not remove) a random item
	public Item sample(){
		int r = rand.nextInt(count);
		return items[r];
	}

	// remove and return a random item
	public Item dequeue(){
	
		int r = rand.nextInt(count);
		Item temp = items[r];
		items[r] =items[--count];
		items[count]= null;
		
		if(count < size()/4)
			rebuild(size()/2);
			
		return temp;
	}
	// return an iterator over the items in random order
	public Iterator<Item> iterator() {
		return new RandomQueueIterator();
	}
	
	// An iterator for the random queue
	private class RandomQueueIterator implements Iterator<Item>{
		
		private int i;// Indicates the end of the subarray to iterate over
		Item[] temps;// Temporary copy of the original queueu
		
		//Constructor for the iterator
		public RandomQueueIterator(){
			i = count;
			temps = (Item[]) new Object[size()];
			for(int j = 0; j < count; j++){
				temps[j]=items[j];
			}
		}
		
		//Are there any more elements to iterate over ?
		public boolean hasNext(){
			return i > 0;
		}
		
		//Returns a random element and puts the element out of scope for the iterator
		public Item next(){
			int r = rand.nextInt(i);
			Item temp = temps[r];
			temps[r] =temps[--i];
			temps[i]= null;
			
			return temp;
		}
		
		//Not implemented
		public void remove(){}
	}

}